package com.demo.datastructure.linkedlist;

/**
 * 单链表 带头结点
 */
public class MySingleLinkedList {

    public Node head = new Node(0, null);

    /**
     * 尾插法 顺序
     *
     * @param val
     */
    public void insertTail(int val) {
        Node tmp = head;
        Node newNode = new Node(val);

        if (head.next == null) {
            head.next = newNode;
        } else {
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = newNode;
        }
    }

    /**
     * 头插法 逆序
     *
     * @param val
     */
    public void insertHead(int val) {
        Node node = new Node(val);
        node.next = head.next;
        head.next = node;
    }

    public void delete(int val) {
        Node tmp = head.next;

        if (tmp.val == val) {
            head.next = tmp.next;
            return;
        }
        while (tmp != null) {
            if (tmp.next != null && tmp.next.val == val) {
                tmp.next = tmp.next.next;
                return;
            }
            tmp = tmp.next;
        }
        System.out.println("no val = " + val + " in list");
    }

    public Node getNode(int val) {
        Node tmp = head.next;
        Node retNode = null;
        while (tmp != null) {
            if (tmp.val == val) {
                retNode = tmp;
                break;
            }

            tmp = tmp.next;
        }

        return retNode;
    }

    /**
     * p 节点后插入新节点
     *
     * @param newNode
     * @param p
     */
    public void insertAfter(Node newNode, Node p) {
        Node tmp = head.next;

        if (p == null) {
            return;
        }
        while (tmp != null) {
            if (tmp == p) {
                newNode.next = p.next;
                p.next = newNode;
                break;
            }
            if (tmp.next == p) {
                newNode.next = p.next;
                p.next = newNode;
                break;
            }
            tmp = tmp.next;
        }
    }

    public void insertBefore(Node newNode, Node p) {
        Node tmp = head.next;
        if (p == null) {
            return;
        }
        while (tmp != null) {
            if (tmp == p) {
                newNode.next = p;
                head.next = newNode;
                break;
            }

            if (tmp.next == p) {
                newNode.next = p;
                tmp.next = newNode;
                break;
            }
            tmp = tmp.next;
        }
    }

    /**
     * 合并两个有序链表 合并后仍保持有序
     * @param list1
     * @param list2
     * @return
     */
    public MySingleLinkedList mergerSortedList(MySingleLinkedList list1, MySingleLinkedList list2) {

        MySingleLinkedList retList = new MySingleLinkedList();
        if (list1 == null && list2 != null)
        {
            retList = list2;
        }
        if (list2 == null && list1 != null)
        {
            retList = list1;
        }

        if (list1 != null && list2 != null)
        {
            // 递归调用从list1 和 list2中获取最小的值添加到 retList中
            /**
             *  1.递归推导式：newList->next = f(minNode) = min(list1.node,list2.node)
             *  f(minNode)->f(minNode-next)
             *  2.递归结束条件：任何一个list为null
             *  3.代码实现：
             */
            retList.head.next = mergerNode(list1.head.next, list2.head.next);
        }
        return retList;
    }

    /**
     * 递归调用求list1 list2中最小值得node
     * @param node1
     * @param node2
     * @return
     */
    private Node mergerNode(Node node1,Node node2)
    {
        Node retNode;
        // 递归结束条件
        if (node1 == null)
        {
            return node2;
        }
        // 递归结束条件
        if (node2 == null)
        {
            return node1;
        }
        if (node1.val < node2.val)
        {
            retNode = node1;
            retNode.next = mergerNode(node1.next,node2);
        }else
        {
            retNode = node2;
            retNode.next = mergerNode(node1,node2.next);
        }
        return retNode;
    }

    /**
     * 链表反转 1 3 4 6 9
     */
    public MySingleLinkedList reversal(Node node) throws Exception {
        MySingleLinkedList retList = new MySingleLinkedList();
        if (node == null)
        {
            throw new Exception("链表为空");
        }
        Node insertNode = node;
        /**
         * 使用头插法重新插入一次即可解决
         */
        while (insertNode != null)
        {
            Node tmpNode = new Node(insertNode.val);
            tmpNode.next = retList.head.next;
            retList.head.next = tmpNode;

            insertNode = insertNode.next;
        }

        return retList;
    }
    /**
     * 使用链表判断是否是回文串
     * 分回文串的个数为奇偶情况
     * @param list 回文串如 leael
     * @return
     */
    public boolean isPalindrome(MySingleLinkedList list)
    {
        // 一个链表每次移动一步 另一个每次移动2步
        return true;
    }

}
